package com.fan.leetcode;

import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 802. 找到最终的安全状态
 *
 * @author ZhangFan
 * @since 2021/8/5 下午 10:19
 */
public class Question802 {
    @Test
    void test() {
        System.out.println(eventualSafeNodes(new int[][]{{1, 2}, {2, 3}, {5}, {0}, {5}, {}, {}}));
    }

    public List<Integer> eventualSafeNodes(int[][] graph) {
        List<Integer> list = new ArrayList<>();
        int size = 0;
        for (int i = 0; i < graph.length; i++) {
            if (graph[i].length == 0) {
                list.add(i);
            }
        }
        do {
            size = list.size();
            for (int i = 0; i < graph.length; i++) {
                if (list.contains(i)) {
                    continue;
                }
                boolean flag = true;
                for (int anInt : graph[i]) {
                    if (!list.contains(anInt)) {
                        flag = false;
                        break;
                    }
                }
                if (flag && !list.contains(i)) {
                    list.add(i);
                }
            }
        } while (list.size() != size);
        Collections.sort(list);
        return list;
    }
}
